package com.tianyuan.test1;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**堆/栈/队列*/
/**
 * 用两个栈实现队列
 *
 * @date 2025/10/17 10:47
 * 利用栈“先进后出”的特性，通过两个栈的反转操作,模拟队列"先进先出"的特性
 * @date 2025/10/17 10:47
 *
 * 输入：["PSH1","PSH2", "POP","POP"]
 * 返回值：1，2
 * 输入：["PSH2", "POP", "PSH1","POP"]
 * 返回值：2，1
 *
 * 说明：
 * "PSH1"：代表将1插入队列尾部 "PSH2"：代表将2插入队列尾部    (PSH 是 “存数据”，按顺序堆在队列尾部)
 * "POP"：代表删除一个元素，先进先出=>返回1                  (POP 是 “取数据”，必须从队列头部取（先存的先取）)
 * "POP"：代表删除一个元素，先进先出=>返回2                  (POP 移除并返回)
 */
public class Solution {
    // 栈1：专门用于“入队”操作（存储新添加的元素）
    Stack<Integer> stack1 = new Stack<Integer>();
    // 栈2：专门用于“出队”操作（存储待取出的元素，顺序已反转）
    Stack<Integer> stack2 = new Stack<Integer>();
    /**
     * 队列的“入队”方法：添加元素到队列尾部
     * @param node 要加入队列的整数元素
     */
    public void push(int node) {
        // 直接将元素压入栈1，栈1只负责接收新元素，符合栈“先进后出”的压栈逻辑
        stack1.push(node);
    }
    /**
     * 队列的“出队”方法：从队列头部取出元素
     * @return 队列头部的元素（若队列为空，返回默认值0）
     */
    public int pop() {
        // 第一步：如果栈2为空，将栈1中所有元素“倒”到栈2中
        // 目的：反转元素顺序——栈1中“先进后出”的元素，倒入栈2后变为“先进先出”（符合队列逻辑）
        if(stack2.isEmpty()){
            // 循环弹出栈1的元素，逐个压入栈2，直到栈1为空
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        // 第二步：判断栈2是否仍为空（若为空，说明栈1也为空，整个队列为空）
        // 避免直接调用stack2.pop()时抛出空栈异常，此时返回默认值0
        if(stack2.isEmpty()) return 0;

        // 第三步：从栈2弹出元素（栈2顶部元素就是队列的头部元素）
        return stack2.pop();
    }









    public static void main(String[] args) {
        Solution queue = new Solution();
        // 测试用例1：["PSH1","PSH2", "POP","POP"]，预期输出：1，2
        System.out.println("测试用例1：");
        // 解析命令并执行
        String[] commands1 = {"PSH1", "PSH2", "POP", "POP"};
        List<Integer> results1 = new ArrayList<>();
        for (String cmd : commands1) {
            if (cmd.startsWith("PSH")) {
                // 提取数字并执行入队操作（如"PSH1"提取1）
                int num = Integer.parseInt(cmd.substring(3));
                queue.push(num);
                System.out.println("执行入队：" + num);
            } else if (cmd.equals("POP")) {
                // 执行出队操作并记录结果
                int res = queue.pop();
                results1.add(res);
                System.out.println("执行出队：" + res);
            }
        }
        System.out.println("测试用例1结果：" + results1 + "\n");
        // 重置队列（重新创建对象，避免影响下一个测试用例）
        queue = new Solution();
        // 测试用例2：["PSH2", "POP", "PSH1","POP"]，预期输出：2，1
        System.out.println("测试用例2：");
        String[] commands2 = {"PSH2", "POP", "PSH1", "POP"};
        List<Integer> results2 = new ArrayList<>();
        for (String cmd : commands2) {
            if (cmd.startsWith("PSH")) {
                int num = Integer.parseInt(cmd.substring(3));
                queue.push(num);
                System.out.println("执行入队：" + num);
            } else if (cmd.equals("POP")) {
                int res = queue.pop();
                results2.add(res);
                System.out.println("执行出队：" + res);
            }
        }
        System.out.println("测试用例2结果：" + results2);
    }
}